class Solution {
public:
    int get(vector<int> &num, int l, int r) {
        int ans = 0;
        for (int i = l; i >= r; i--) {
            ans = ans * 10 + num[i];
        }
        return ans;
    }
    int p(int n) {
        int ans = 1;
        while (n--) ans *= 10;
        return ans;
    }
    int dp(int n, int x) {
        if (n == 0) return 0;
        vector <int> num(1);
        while (n) {
            num.push_back(n % 10);
            n /= 10;
        }
        int k = num.size() - 1, ans = 0;
        for (int i = k - !x; i >= 1; i--) {
            if (i != k) ans += (get(num, k, i + 1) - !x) * p(i - 1);
            if (x == num[i]) ans += get(num, i - 1, 1) + 1;
            else if (x < num[i]) ans += p(i - 1);
        }
        return ans;
    }
    int countDigitOne(int n) {
        return dp(n, 1);
    }
};
